#include<stdio.h>
#include <malloc.h>
#define OK 1 
#define ERROR 2
#define FULL 3
#define MAX_SIZE 100
typedef int Status;
typedef int ElemType;
/*
typedef struct sqlist{
    ElemType Elem_array[MAX_SIZE];
 	int length;
}SqList;
*/


typedef struct sqlist
{
	ElemType *elem_array; //存储数组
	int length;  //表中当前元素
	int maxSize;  //最大容量
}SqList;

Status Init_SqList(SqList *L)
 {
 	/* int 4B
 	   char 1B
 	   double 8B
 	*/

 	L ->elem_array = (ElemType *)malloc(MAX_SIZE*sizeof(ElemType));
 	/*开辟一段连续的内存空间，长度为EleType类型的MAX_SIZE倍,强制转换成Elemtype类型,
 	将首地址赋值给 L结构体的elem_array指针的首地址*/
 	if (!L -> elem_array)  //没有足够内存返回为0，即为！0
 	{
 		return ERROR;
 	}
 	else
 	{
 		L -> length = 0;
 		return OK;
 	}

 }
 		
/*
	插入：
	1.将线性表L中的第i个至第n个元素后移动一位;
	2.将结点e插入到i-1后面;
	3.线性表长度加1.

	插入的时间复杂度根据插入的位置变换 最大为n 最小为1
*/

Status Insert_SqList(SqList *L,int i ,ElemType e)
{
	int j;
	if (i < 0 ||  i >(L -> length+1) )//插入的位置判断
		return ERROR;
	if (L -> length >= MAX_SIZE) //元素个数是否满了
	{
		printf("溢出！\n");
		return FULL;
	}

	for (j = L->length-1 ; j >= i-1 ; --j)
	{
		L -> elem_array[j+1] = L -> elem_array[j];
		//i-1后的所有元素后移
	}

	L -> elem_array[i-1] = e;

	L -> length++;

	return OK;
}

ElemType Delete_SqList(SqList *L, int i)
{
	ElemType x;
	int k;
	if (L -> length == 0)
		return ERROR;
	else if (i < 0 || i > L -> length)
		return ERROR;
	else
		x = L -> elem_array[i-1];

	for (k=i; k <= L -> length; k++)
	{
		L -> elem_array[k-1] = L -> elem_array[k];
	}

	L -> length--;
	return(x);
}

/*
	顺序表按值查找元素位置
*/

Status Locate_Delete_SqList(SqList *L,ElemType x)
{
	int i=0,k;

	if (L -> elem_array[i] != x)
		i++;
	else
	{
		for (k = i; k < L -> length ; k++)
		{
			L -> elem_array[k] = L -> elem_array[k+1];
		}
		L -> length--;
	}

	if (i > L -> length)
	{
		printf("要删除的数据元素不存在\n");
		return ERROR;
	}

	return OK;
}

void MergerList_SqList(SqList *La, SqList *Lb, SqList *Lc)
{
	int i,j,k;
	i = j = k = 0;
	while (i < La -> length && j < Lb -> length)
	{
		if (La -> elem_array[i] < Lb -> elem_array[j])
		{
			Insert_SqList(Lc,k++,La -> elem_array[i++]);
		}
		else 
		{
			Insert_SqList(Lc,k++,Lb -> elem_array[j++]);
		}
	}

	while (i == La -> length)
	{	
		if (j < Lb -> length)
		{
			Insert_SqList(Lc,k++,Lb -> elem_array[j++]);
		}
		else
			break;
	}

	while (j == Lb -> length)
	{	
		if (i < La -> length)
		{
			Insert_SqList(Lc,k++,La -> elem_array[i++]);
		}
		else
			break;
	}

}

void test(int n)
{
	int a[n];
	a[n-n] = 0;
	a[n-1] = 1;
	printf("--------%d\n",a[n-1]);
}

int Majority(int a[],int n)
{
	int max1;
	//int i;
	max1 = a[0];
	printf("------------------%d\n",max1);
	for (int i = 0;i < n;i++)
	{
		if (max1 < a[i+1])
			max1 = a[i+1];
	}

	int k,p;
	k = max1;
	int b[k+1];
	

	for (int i = 0;i < n;i++)
	{
		p = a[i];
		b[p] = b[p] + 1;

	}
	//int q;
	int max2;
	max2 = b[0];
	for (int i = 0;i < k+1;i++)
	{
		if (max2 < b[i+1])
			max2 = b[i+1];
	}

	if (max2 <= n/2)
	{
		printf("无主元素\n");
	}
	else
	{
		return max2;
	}
}

int main(void)
{	

	int a[8];
	a[0]=0;
	a[1]=5;
	a[2]=5;
	a[3]=3;
	a[4]=5;
	a[5]=7;
	a[6]=5;
	a[7]=5;
	printf("主元素是%d\n",Majority(a,8));


	/*
	int b,c,d;
	struct sqlist a;

	b = Init_SqList(&a);

	c =Insert_SqList(&a,1,2);

	d = Delete_SqList(&a,1);

	printf("%d\n",a.length);

	printf("%d    %d  %d  %d\n",b,c,d,a.elem_array[0]);
	*/

	/*
	struct sqlist La;
	struct sqlist Lb;
	struct SqListlist Lc;

	printf("初始化状态为%d\n",Init_SqList(&La));
	printf("初始化状态为%d\n",Init_SqList(&Lb));
	printf("初始化状态为%d\n",Init_SqList(&Lc));
	*/

}